The present invention relates to a method of simulating detailed movements of fluids using derivative particles.
1. Introduction
When water interacts violently with solids, air, or water itself, it takes on a variety of structures, including droplets/bubbles, thin water sheets, and whirlpools, as shown in FIG. 7. Such features can appear when fluids undergo motions characterized by high Reynolds numbers, where the Reynolds number represents the relative magnitude of the inertia compared to the viscosity of the fluid. Fast-moving water is a typical high-Reynolds-number fluid. The invention explores the physically-based simulation of such phenomena.
Assuming that the Navier-Stokes equations correctly model the physical movements of fluids, a plausible simulation should be able to reproduce the high-Reynolds-number behaviors of water. Although the present work focuses on water, it can apply to any fluid. To date, however, these phenomena have not been satisfactory reproduced. The invention identifies the factors underlying this failure, and proposes a method that allows realistic simulation of high-Reynolds-number liquid motions.
Implausible simulation of high-Reynolds-number fluids is related to numerical dissipation. Specifically, discretized simulation of the Navier-Stokes equations inevitably calls for evaluating physical quantities at non-grid points. In most methods, such values are calculated by interpolation of the values of the physical quantities at the grid points. However, the error introduced by this approximation acts like nonphysical viscosity or numerical dissipation. This dissipation can be reduced by using a finer grid; however, increasing the grid resolution may increase the computation time and memory requirements to impractical levels. Over the last few years, several elegant techniques have been proposed to address this issue. Bringing in particles into the Eulerian scheme can help capture the inertial movement of fluids, and increases the effective resolution of the simulation. Enright et al. [2002b] introduced the particle level set method, which increases the accuracy of surface tracking by spreading particles around the interface. Losasso et al. [2004] proposed an octree-based multi-level fluid solver that allows finer-resolution simulations in more interesting regions such as water surfaces.
Unfortunately, the above techniques cannot produce high-Reynolds-number liquids with sufficient detail and realism. The simulated fluid appears more viscous than in real physics; the fluids often look thick/sticky, and the movements of small-scale features that are typically observed in complex flows do not appear. The applicants find that the reason the above dissipation-suppressing techniques produce this sort of artifacts is because they cannot effectively suppress the velocity-dissipation, even though they reduce the mass dissipation remarkably.
In the present invention, the applicants introduce a new concept called derivative particles, and develop a fluid simulator based on that concept. The applicants take advantage of the non-dissipative nature of the Lagrangian scheme for the simulation of the advection part; for fluid regions where details need to be simulated, the applicants solve the advection step using particles. Switching between the grid-based and particle-based simulators can introduce numerical dissipation. The present invention develops a new conversion procedure that allows the reproduction of detailed fluid movements. One innovative aspect of this work is that, in addition to storing the physical quantities (velocity and level set value), the derivative particles also store the spatial derivatives of those quantities, which enables more accurate evaluation of the physical quantities at non-grid/non-particle positions. The use of particles in the present work differs from the particle level set method [Enright et al. 2002b] in that the derivative particles carry fluid velocities as well as level set values.
Experiments show that the proposed simulator tracks interfaces accurately. More interestingly, the proposed method turns out to reduce nonphysical damping to a remarkable extent, allowing the reproduction of the magnificent movements of small scale features that occur in real high-Reynolds-number fluids.
The remainder of the specification is organized as follows: Section 2 reviews previous work; Section 3 gives an overview of the simulator; Section 4 presents the octree-based constrained interpolation profile (CIP) solver; Section 5 presents the derivative particle model; Section 6 reports our experimental results; and Section 7 concludes the specification.
2. Previous Work
Since Foster and Metaxas [1996; 1997] first introduced fluid animation techniques based on full 3D Navier-Stokes simulation, the approach has spread widely among the computer graphics community. Jos Stam [1999] introduced a stable fluid solver known as Stable Fluids. The advection step of this solver was implemented using a semi-Lagrangian method [Staniforth and C^ot{grave over ( )}e 1991], which remains stable even when large time steps are used. Since then, there have been active developments of fast fluid animation techniques in computer graphics, based on the semi-Lagrangian method. Rasmussen et al. [2003] proposed a technique to produce 3D large scale animations of gases using a 2D semi-Lagrangian solver, and Feldman et al. [2003] proposed an explosion model that incorporates a particle-based combustion model into the Stable Fluids solver. Treuille et al. [2003; 2004] introduced an optimization technique that generates the fluid flows that meet specified keyframe constraints. In addition, Feldman et al. proposed the use of a hybrid grid that combines a staggered grid and an unstructured grid [Feldman et al. 2005a], and also proposed the use of a deformable grid [Feldman et al. 2005b], for which they had to modify the semi-Lagrangian method.
In order to simulate liquids, a model for tracking the liquid surfaces is needed in addition to a stable Navier-Stokes solver. For this purpose, Foster and Fedkiw [2001] proposed a hybrid surface model in which massless particles are introduced to the level set field. This model motivated the development of the particle level set method [Enright et al. 2002b], which can capture the dynamic movements of fluid surfaces with remarkable accuracy. Enright et al. [2005] demonstrated that the particle level set method allows the use of large time steps in the semi-Lagrangian framework. The method has been employed to model the interactions between fluids and rigid bodies [Carlson et al. 2004] and between fluids and deformable thin-shell objects [Guendelman et al. 2005], as well as to animate viscoelastic fluids [Goktekin et al. 2004], sand [Zhu and Bridson 2005], multi-phase fluids [Hong and Kim 2005], and water drops [Wang et al. 2005].
As an alternative to the grid-based approaches, purely particle-based methods have also been studied. Stam and Fiume [1995] used smoothed particle hydrodynamics (SPH) to model gaseous phenomena. In SPH, the fluid is represented by a collection of particles, and the simulator calculates movements of them by accounting for each term of the Navier-Stokes equations. M{umlaut over ( )}uller et al. [2003] used the SPH model for simulating liquids, and in [M{umlaut over ( )}uller et al. 2005], they use the technique for simulating multi-phase fluid interactions. Premo^ze et al. [2003] introduced the moving particle semi-implicit (MPS) method to the graphics community, a technique that shows better performance than SPH in simulating the incompressible movements of fluids. However, a fundamental drawback of purely particle-based methods is their lack of a surface tracking capability; if an inappropriate number of particles are used, they can produce grainy or overly smoothed surfaces.
A primary factor that impairs the visual realism (and also the physical accuracy) of simulated results is the numerical dissipation of the velocity field. To reduce the dissipation when simulating gaseous phenomena, Fedkiw et al. [2001] used cubic interpolation. They also included an additional step referred to as vorticity confinement that amplifies the curl of the velocity field, producing realistic swirly components in smoke movements. More physically based prevention of the vorticity dissipation was done [Selle et al. 2005; Park and Kim 2005] by employing the the vortex particle method. This method works with the curl version of the Navier-Stokes equations and utilizes particles to solve the advection term, which results in effective preservation of the vorticities. In the case of liquids, however, viscosity plays a more prominent role; in particular, swirly movements are short-lived and less frequently observed. Thus, modeling the behavior of high-Reynolds-number liquids requires a velocity-dissipation suppression technique that works in more general situations. To reduce dissipation in liquid simulations, Song et al. [2005] proposed a technique based on the CIP advection method. Their technique solves the velocity advection with third-order accuracy. However, the numerical viscosity that is coming from the grid-based advection cannot be avoided by this approach. Zhu and Bridson [2005] proposed a fluid simulation technique based on the FLuid-Implicit-Particle (FLIP) method. The FLIP method [Brackbill and Ruppel 1986] solves the advection step with particles, but all other steps on the grid. Although the particle advection in this method is free from numerical dissipation, interpolation errors are introduced when the velocity values are transferred back and forth between the grid and particles.
Accordingly, a need for a method of simulating detailed movements of fluids using derivative particles has been present for a long time. This invention is directed to solve these problems and satisfy the long-felt need.